/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***使用单向链表实现一个栈                       ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
using std::cout;
using std::endl;

template <class T>

class LinkedStack
{
public:
    LinkedStack()
    {
    }
    bool isEmpty()
    {
        return top == nullptr;
    }
    void push(T value)
    {
        node *newNode = new node(value, top);
        top = newNode;
    }
    T pop()
    {
        if (top == nullptr)
        {
            cout << "栈为空！" << endl;
            return 0;
        }
        T ret = top->value;
        auto nodeToDel = top;
        top = top->next;
        if (nodeToDel != nullptr)
        {
            delete nodeToDel;
            nodeToDel = nullptr;
        }
        return ret;
    }

    void list()
    {
        if (top==nullptr){
            cout<<"链表为空！"<<endl;
        }
        auto temp=top;
        while (temp!=nullptr)
        {
            cout<<"stack[xx]="<<temp->value<<endl;
            temp=temp->next;
        }
    }

    ~LinkedStack()
    {
        while (top != nullptr)
        {
            auto nodeToDel = top;
            if (top->next != nullptr)
            {
                top = top->next;
            }
            if (nodeToDel != nullptr)
            {
                delete nodeToDel;
                nodeToDel = nullptr;
            }
        }
    }

private:
    typedef struct node
    {
        T value;
        node *next;
        node(T value) : value(value), next(nullptr) {}
        node(T value, node *next) : value(value), next(next) {}
    } node;
    node *top = nullptr;
};

int main(int argc, char **argv)
{
    LinkedStack<int> s1;
    cout << "s1 is empty?" << s1.isEmpty() << endl;
    s1.push(10);
    s1.push(20);
    s1.push(30);
    cout << "s1 is empty?" << s1.isEmpty() << endl;
    // cout << "s1 is full?" << s1.isFull() << endl;
    s1.list();
    cout << s1.pop() << endl;
    cout << s1.pop() << endl;
    cout << s1.pop() << endl;
    cout << "s1 is empty?" << s1.isEmpty() << endl;
    system("pause");
}